package com.demo.jzoffer2;

import com.demo.domain.TreeNode;
import org.junit.Test;

/**
 * @author gy
 * @date 2023/04
 */
public class Test0401_01 {

    /**
     * 解题思路：
     * isSubStructure 函数定义：判断B是否为A的子结构
     * @param A
     * @param B
     * @return
     */
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        // 若 A 与 B其中一个为空，立即返回false
        if (A == null || B == null){
            return false;
        }
        // B为A的子结构有三种情况，满足任意一种情况即可
        // 1、B的子结构起点为A的根节点，此时结果为 recur（A，B）
        // 2、B的子结构起点隐藏在A的左子树中，而不是直接为A的根节点，此时结果为 isSubStructure（A.left,B）
        // 3、B的子结构的起点隐藏在A的右子树中，此时结果为 isSubStructure（A.right,B）
        return recur(A,B) || isSubStructure(A.left,B) || isSubStructure(A.right,B);
    }

    /**
     * 判断 B 是否为 A的子结构，
     * 此时：其中 B子结构的起点为 A的根节点
     * @param A
     * @param B
     * @return
     */
    private boolean recur(TreeNode A, TreeNode B){
        // 若B走完了，说明查找完毕，B为A的子结构
        if (B == null){
            return true;
        }
        // 若B不为空并且A为空 或者A与B的值不相等，直接可以判断 B不是A的子结构
        if (A == null || A.val != B.val){
            return false;
        }
        // 当A与B当前节点值相等，若要判断B为A的子结构
        // 还需要判断B的左子树是否为A左子树的子结构 && B的右子树是否为A右子树的子结构
        // 若两者都满足说明 B是A的子结构，并且该子结构以A根节点为起点
        return recur(A.left,B.left) && recur(A.right,B.right);
    }

    @Test
    public void m1() {

    }

    @Test
    public void m2() {
        }

    @Test
    public void m3() {

    }



}
